package com.topcoder.srm497;

/**
 * A string is called a square if it is the concatenation of two copies of 
 * the same string.
 * 
 * For example, strings abcabc and aaaa are squares, strings aaa, abcab, 
 * and defgh are not. 
 * 
 * Given a string S, a step is one of the following changes:
 *
 *  1. Changing a single letter in S to any other letter.
 *  2. Erasing a single letter from S.
 *  3. Adding one new letter anywhere into S, including the beginning or the 
 *     end of S.
 *  
 * For example, if S=abaca, then each of the strings abeca, baca, abafca, 
 * and gabaca can be reached from S in a single step. You need at least two 
 * steps to reach the string bac, at least four steps to reach the string dafg, 
 * and at least five steps to reach the empty string.
 * 
 * You are given a String S. Return the smallest number of steps necessary to 
 * change S into a square.  
 */
public class MakeSquare {
	public int minChanges(String S) {
		int min = S.length();
		for (int i=1; i<S.length(); i++) {
			min = Math.min(min, dp(S.substring(0, i), S.substring(i)));
		}
		return min;
	}
	
	private int dp(String a, String b) {
		int N = a.length();
		int M = b.length();
		int[][] T = new int[N+1][M+1];
		
		for (int i=0; i<=N; i++) T[i][0] = i;
		for (int i=0; i<=M; i++) T[0][i] = i;
		
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=M; j++) {
				T[i][j] = Math.min(T[i][j-1] + 1, T[i-1][j] + 1);
				if (a.charAt(i-1) == b.charAt(j-1)) {
					T[i][j] = Math.min(T[i][j], T[i-1][j-1]);
				}
				else {
					T[i][j] = Math.min(T[i][j], T[i-1][j-1] + 1);
				}
			}
		}
		
		return T[N][M];
	}
}
